package com.cat.dynamicPlanning02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
 * @create 2025/10/13 16:52
 * @since JDK17
 */

public class Solution19 {

    long limit;
    int n;
    int[] nums, dp;

    boolean dfs(int status, int cur, int rest) {
        if (rest == 0) {
            return status == 0; // 全部用完
        }
        if (dp[status] != 0) {
            return dp[status] == 1;
        }
        boolean ans = false;
        for (int i = 0; i < n; i++) {
            if ((status & (1 << i)) != 0 && cur + nums[i] <= limit) {
                if (cur + nums[i] == limit) {
                    ans = dfs(status ^ (1 << i), 0, rest - 1);
                } else {
                    ans = dfs(status ^ (1 << i), cur + nums[i], rest);
                }
                if (ans) {
                    break;
                }
            }
        }
        dp[status] = ans ? 1 : -1;
        return ans;
    }
    public boolean canPartitionKSubsets(int[] nums, int k) {
        long sum = 0;
        n = nums.length;
        for (int num : nums) {
            sum += num;
        }
        if (sum % k != 0) {
            return false;
        }
        limit = sum / k;
        dp = new int[1 << n];
        this.nums = nums;

        return dfs((1 << n) - 1, 0, k);
    }
}
